package com.leetcode;

import java.util.Arrays;
import java.util.Hashtable;

@SuppressWarnings("all")
public class LeetCode {
    /**
     * 两数之和
     */
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i]+nums[j]==target) {
                    int[] ints = new int[2];
                    ints[0]=i;
                    ints[1]=j;
                    return ints;
                }
            }
        }
        return null;
    }

    /**
     * 不能使用排序解决问题
     */
    public int[] twoSum2(int[] nums, int target) {
        Arrays.sort(nums);
        int left=0 ,right =nums.length-1;
        int[] ints = new int[2];
        for (;left<right;) {
           int temp = nums[left] + nums[right];
           if (temp==target) {
               ints[0]=left; ints[1] =right;
               return ints;
           }
           if (temp>target) {
               right--;
           }
           if (temp<target) {
               left++;
           }
        }
        return null;
    }

    public int[] twoSum3(int[] nums, int target) {
        Hashtable<Integer, Integer> hashtable = new Hashtable<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashtable.containsKey(target-nums[i])) {
                return new int[]{hashtable.get(target-nums[i]),i};
            }
            hashtable.put(nums[i],i);
        }
        return null;
    }

}
